Today's consumers enjoy the ability to access a tremendous amount of media content, such as music and videos, at any location or time of day, using a wide variety of media devices. In a media content environment which supports playlists of media content items, such as songs, music, videos, or other types of media content, whenever a user selects shuffled play of a number of media content items, for example within an artist page or a playlist, the resultant play order of those media content items should appear somewhat random. Additionally, the shuffling should be sufficiently stable so that, for example, the addition or deletion of songs to a playlist by another person actively curating that playlist, has minimal disruption on the listening experience. These are some examples of the types of environments in which embodiments of the invention can be used.